//Given an array of strings words (without duplicates), return all the 
//concatenated words in the given list of words. 
//
// A concatenated word is defined as a string that is comprised entirely of at 
//least two shorter words (not necesssarily distinct) in the given array. 
//
// 
// Example 1: 
//
// 
//Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog",
//"hippopotamuses","rat","ratcatdogcat"]
//Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
//Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
//"dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
//"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat". 
//
// Example 2: 
//
// 
//Input: words = ["cat","dog","catdog"]
//Output: ["catdog"]
// 
//
// 
// Constraints: 
//
// 
// 1 <= words.length <= 10⁴ 
// 1 <= words[i].length <= 30 
// words[i] consists of only lowercase English letters. 
// All the strings of words are unique. 
// 1 <= sum(words[i].length) <= 10⁵ 
// 
//
// Related Topics 深度优先搜索 字典树 数组 字符串 动态规划 👍 300 👎 0

package leetcode.editor.cn;
class P472ConcatenatedWords{
    //2023-09-09 10:39:02
    //Concatenated Words
    //编号：[472]
    
    public static void main(String[] args) {
    
        Solution solution = new  P472ConcatenatedWords().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {

}
//leetcode submit region end(Prohibit modification and deletion)

}